/**
 * 
 * @param {number[]} arr 
 */

function insertSort(arr) {
    // 初始化数组
    const len = arr.length
    // 用来标记需要插入的值
    let temp
    // 从第二个元素开始 因为第一个元素已经是有序的
    for (let i = 1; i < len; i++) {
        let j = i
        // 记录当前元素的值，便于移动数组
        temp = arr[i]
        // 只要j没有越界 并且 前面的元素大于后面的元素
        while (j > 0 && arr[j - 1] > temp) {
            // 向后移一位
            arr[j] = arr[j - 1]
            j--
        }
        arr[j] = temp
    }
    return arr
}

console.log(insertSort([5, 4, 3, 2, 1]))